import java.util.*;

public class project {
    public int findMaximumXOR(int[] nums) {
        int ret=0;
        for(int i=30;i>=0;i--){
            Set<Integer> set=new HashSet<>();
            for(int num:nums){
                set.add(num>>i);
            }
            int next=ret*2+1;
            boolean flag=false;
            for(int num:nums){
                if(set.contains(next^(num>>i))){
                    flag=true;
                    break;
                }
            }
            if(flag){
                ret=next;
            }else{
                ret=next-1;
            }
        }
        return ret;
    }



















    public int findMaximumXOR1(int[] nums) {
        int bit=30;
        int x=0;
        for(int i=bit;i>=0;i--){
            Set<Integer> set=new HashSet<>();
            for(int num:nums){
                set.add(num>>i);
            }
            int next=x*2+1;
            boolean flag=false;
            for(int num:nums){
                if(set.contains(next^(num>>i))){
                    flag=true;
                    break;
                }
            }
            if(flag){
                x=next;
            }else{
                x=next-1;
            }
        }
        return x;
    }
























    List<String> list=new LinkedList<>();
    public List<String> restoreIpAddresses(String s) {
        char[] ch=s.toCharArray();
        if(ch.length<4){
            return list;
        }
        dfs(ch,"",0,0);
        return list;
    }
    public void dfs(char[] ch,String str,int index,int size){
        if(size==4&&ch.length==index){
            list.add(str.substring(0,str.length()-1));
            return;
        }
        if(size==4||ch.length==index){
            return;
        }
        int sum=0;
        for(int i=index;i<ch.length;i++){
            sum+=ch[i]-'0';
            if(i-index>0&&ch[index]-'0'==0){
                break;
            }
            if(sum>255){
                break;
            }
            dfs(ch,str+sum+'.',i+1,size+1);
            sum*=10;
        }
    }



















    List<String> list1=new LinkedList<>();
    public List<String> restoreIpAddresses1(String s) {
        char[] ch=s.toCharArray();
        if(ch.length<4){
            return list1;
        }
        dfs1(ch, "",0,0);
        return list1;
    }
    public void dfs1(char[] ch,String str,int index,int size){
        if(size==4&&index==ch.length){
            list1.add(str.substring(0,str.length()-1));
            return;
        }
        if(size==4||index==ch.length){
            return;
        }
        int sum=0;
        for(int i=index;i<ch.length;i++){
            sum+=ch[i]-'0';
            if(i-index>0&&ch[index]-'0'==0){
                break;
            }
            if(sum>255){
                break;
            }
            dfs1(ch,str+sum+'.',i+1,size+1);
            sum*=10;
        }
    }














    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Arrays.sort(products);
        List<List<String>> list=new LinkedList<>();
        for(int i=1;i<=searchWord.length();i++){
            String section=searchWord.substring(0,i);
            List<String> row=new LinkedList<>();
            int size=0;
            for(String product:products){
                if(product.indexOf(section)==0&&size<3){
                    size++;
                    row.add(product);
                }
            }
            list.add(row);
        }
        return list;
    }















    public String toGoatLatin(String sentence) {
        String[] str=sentence.split(" ");
        String contrast="aeiouAEIOU";
        String countA="a";
        String ma="ma";
        List<String> list=new LinkedList<>();
        for(String s:str){
            int len=s.length();
            StringBuilder sb=new StringBuilder();
            boolean flag=false;
            for(int i=0;i<len;i++){
                char ch=s.charAt(i);
                if(!contrast.contains(ch+"")&&i==0){
                    flag=true;
                }else{
                    sb.append(ch);
                }
            }
            if(flag){
                sb.append(s.charAt(0));
            }
            sb.append(ma+countA);
            countA=countA+"a";
            list.add(sb.toString());
        }
        StringBuilder ret=new StringBuilder();
        for(int i=0;i<list.size();i++){
            if(i==list.size()-1){
                ret.append(list.get(i));
            }else{
                ret.append(list.get(i)+" ");
            }
        }
        return ret.toString();
    }

}
